class CommonSubString:
	def maxPrefix(self, s1, s2):
		i = 0
		while i < len(s1) and i < len(s2):
			if list(s1)[i] == list(s2)[i]:
				i += 1
			else:
				break
		return i
	
	def getMaxCommonStr(self, txt):
		n = len(txt)
		suffixes = [None] * n
		longestSubStrLen = 0
		longestSubStr  = None
		i = 0
		while i < n:
			suffixes[i] = txt[i:]
			i += 1
		suffixes.sort()
		i = 1
		while i < n:
			tmp = self.maxPrefix(suffixes[i], suffixes[i-1])
			if tmp > longestSubStrLen:
				longestSubStrLen = tmp
				longestSubStr = suffixes[i][0:tmp]
			i += 1
		return longestSubStr